package com.sheng.leetcode.year2023.month08.day08;

import org.junit.Test;

/**
 * @author by ls
 * @date 2023/8/9
 * <p>
 * 1749. 任意子数组和的绝对值的最大值<p>
 * <p>
 * 给你一个整数数组 nums 。一个子数组 [numsl, numsl+1, ..., numsr-1, numsr]<p>
 * 的和的绝对值 为 abs(numsl + numsl+1 + ... + numsr-1 + numsr) 。<p>
 * 请你找出 nums 中 和的绝对值 最大的任意子数组（可能为空），并返回该 最大值 。<p>
 * abs(x) 定义如下：<p>
 * 如果 x 是负整数，那么 abs(x) = -x 。<p>
 * 如果 x 是非负整数，那么 abs(x) = x 。<p>
 * <p>
 * 示例 1：<p>
 * 输入：nums = [1,-3,2,3,-4]<p>
 * 输出：5<p>
 * 解释：子数组 [2,3] 和的绝对值最大，为 abs(2+3) = abs(5) = 5 。<p>
 * <p>
 * 示例 2：<p>
 * 输入：nums = [2,-5,1,-4,3,-2]<p>
 * 输出：8<p>
 * 解释：子数组 [-5,1,-4] 和的绝对值最大，为 abs(-5+1-4) = abs(-8) = 8 。<p>
 * <p>
 * 提示：<p>
 * 1 <= nums.length <= 10^5<p>
 * -10^4 <= nums[i] <= 10^4<p>
 */
public class LeetCode1749 {

    @Test
    public void test01() {
//        int[] nums = {1, -3, 2, 3, -4};
        int[] nums = {2, -5, 1, -4, 3, -2};
        System.out.println(new Solution().maxAbsoluteSum(nums));
    }
}

class Solution {
    public int maxAbsoluteSum(int[] nums) {
        // 获取连续子数组中平均和最大或者最小的值，然后进行比较
        // 防止超出边界
        int max = Integer.MIN_VALUE / 2, min = Integer.MAX_VALUE / 2;
        int ans = 0;
        for (int num : nums) {
            max = Math.max(max + num, num);
            min = Math.min(min + num, num);
            ans = Math.max(max, Math.max(-min, ans));
        }
        return ans;
    }
}
